package org.basis.algorithm.sort;

import org.basis.algorithm.common.SortUtil;

/**
 * 二分查找
 *
 * @author Mr_wenpan@163.com 2021/12/02 17:45
 */
public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        SortUtil.printArr(arr);
        System.out.println("result = " + process(arr, -100));

    }

    private static boolean process(int[] arr, int num) {
        if (arr == null || arr.length < 1) {
            return false;
        }
        return doProcess(arr, 0, arr.length - 1, num);
    }

    private static boolean doProcess(int[] arr, int left, int right, int num) {
        // base case
        if (left >= right) {
            return false;
        }
        // 防止溢出
        int mid = left + (right - left) / 2;
        if (arr[mid] == num) {
            return true;
        }
        // 右区间
        if (arr[mid] < num) {
            return doProcess(arr, mid + 1, right, num);
        } else {
            return doProcess(arr, left, mid, num);
        }
    }
}
